package com.lfg.leetcode.leetcode100;


import com.lfg.leetcode.leetcode0.ListNode;

public class No148sortList {

    public static void main(String[] args) {
        ListNode ret = sortList(ListNode.deserialize("[3,2,1,6,5,-1]"));
        System.out.println(ret);
    }

    public static ListNode sortList(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode ret = head;
        ListNode root = head;
        int length = 0;
        while (root != null) {
            length++;
            root = root.next;
        }
        return sortList(head, length);
    }

    public static ListNode sortList(ListNode head, int length) {
        if (head == null) {
            return null;
        }
        if (length == 1) {
            return head;
        }
        ListNode node = subList(head, length / 2);
        ListNode next = node.next;
        node.next = null;
        return merge(sortList(head, length / 2), sortList(next, length - length / 2));
    }

    public static ListNode subList(ListNode head, int length) {
        ListNode ret = head;
        while (--length > 0) {
            ret = ret.next;
        }
        return ret;
    }

    public static ListNode merge(ListNode node1, ListNode node2) {
        if (null == node1 && null == node2) {
            return null;
        }
        if (null == node1) {
            return node2;
        }
        if (null == node2) {
            return node1;
        }
        ListNode ret = null;

        if (node1.val <= node2.val) {
            ret = node1;
            node1 = node1.next;
        } else {
            ret = node2;
            node2 = node2.next;
        }
        ListNode node = ret;
        while (node1 != null && node2 != null) {
            if (node1.val <= node2.val) {
                node.next = node1;
                node1 = node1.next;
            } else {
                node.next = node2;
                node2 = node2.next;
            }
            node = node.next;
        }

        if (node1 != null) {
            node.next = node1;
        }
        if (node2 != null) {
            node.next = node2;
        }

        return ret;
    }
}
